package com.design.pattern;

import lombok.Data;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;


public class Test {
    public static void main(String[] args) {
        int oldArr[]={1,3,4,5,0,0,6,6,0,5,4,7,6,7,0,5};
        System.out.println(Arrays.toString(removeZero(oldArr)));
        int[] a = {1,7,9,11,13,15,17,19};
        int[] b = {2,4,6,8,10};
        System.out.println(Arrays.toString(mergeArray2Sort(a, b)));
        int[] scores = {72,89,65,58,87,91,53,82,71,93,76,68};
        System.out.println(Arrays.toString(count(scores)));
    }

    public static int[] ordinalSearch(int data[],int key){
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < data.length; i++){
            if(data[i] == key){
                list.add(i);
            }
        }
        if(list.size() == 0) return new int[]{-1};
        int[] ret = new int[list.size()];
        for(int i = 0; i < list.size(); i++) ret[i] = list.get(i);
        return ret;
    }
    public static int[] removeZero(int[] arr){
        //two point
        int pre = 0;
        for(int i = 0; i < arr.length; i++){
            if(arr[i]== 0) continue;
            arr[pre] = arr[i];
            ++pre;
        }
        int[] newArr = new int[pre];
        System.arraycopy(arr, 0, newArr, 0, pre);
        return newArr;
    }
    public static int[] mergeArray2Sort(int[] a, int[] b){
        if(a == null||a.length == 0) {
            Arrays.sort(b);
            return b;
        }
        if(b == null || b.length ==0) {
            Arrays.sort(a);
            return a;
        }
        int[] retArr = new int[a.length + b.length];
        System.arraycopy(a, 0, retArr , 0, a.length);
        System.arraycopy(b, 0, retArr , a.length, b.length);
        Arrays.sort(retArr);
        return retArr;
    }

    public static int[] count(int[] scores){
        int[] counts= new int[5];
        for(int score : scores) {
            switch(score / 10) {
                case 9:counts[4]++;break;
                case 8:counts[3]++;break;
                case 7:counts[2]++;break;
                case 6:counts[1]++;break;
                default: counts[0]++;break;
            }
        }
        return counts;
    }

public static int[] bubbleSort(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--) {
        boolean isSort = true;
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                isSort = false;
                swap(arr, j, j + 1);
            }
        }
        if (isSort)
            break;
    }
    return arr;
}

private static void swap(int[] arr, int index1, int index2) {
    arr[index1] ^= arr[index2];
    arr[index2] ^= arr[index1];
    arr[index1] ^= arr[index2];
}

public static int[] insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int j = i - 1;
        int tmp = arr[i];
        for (; j >= 0; j--) {
            if (arr[j] <= tmp)
                break;
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = tmp;
    }
    return arr;
}

public static int[] binaryInsertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int left = 0, right = i - 1;
        int tmp = arr[i];
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] > tmp) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        int j = i - 1;
        while (j >= left)
            arr[j + 1] = arr[j--];
        arr[left] = tmp;
    }
    return arr;
}

public static int[] bucketSort(int[] arr) {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        min = Math.min(min, arr[i]);
        max = Math.max(max, arr[i]);
    }
    int[] buckets = new int[max - min + 1];
    for (int i = 0; i < arr.length; i++) {
        ++buckets[arr[i] - min];
    }
    int j = 0;
    for (int i = 0; i < arr.length;) {
        while (buckets[j] > 0) {
            arr[i++] = j + min;
            --buckets[j];
        }
        ++j;
    }
    return arr;
}

public static int[] selectSort(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--) {
        int largestIndex = i;
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[largestIndex]) {
                largestIndex = j;
            }
        }
        if (largestIndex != i) {
            swap(arr, largestIndex, i);
        }
    }
    return arr;
}

public static int[] quicklySort(int[] arr) {
    qSort(arr, 0, arr.length - 1);
    return arr;
}

private static void qSort(int[] arr, int start, int end) {
    int povit = arr[start], left = start, right = end;
    while (left < right) {
        while (left < right && arr[right] >= povit)
            --right;
        if (left < right)
            arr[left++] = arr[right];
        while (left < right && arr[left] <= povit)
            ++left;
        if (left < right)
            arr[right--] = arr[left];
    }
    arr[left] = povit;
    if (left - start > 1)
        qSort(arr, start, left - 1);
    if(end - right > 1)
        qSort(arr, right + 1, end);
}

public static int[] mergeSort(int[] arr) {
    mSort(arr, 0, arr.length - 1);
    return arr;
}
private static void mSort(int[] arr, int start, int end) {
    if(start < end) {
        int mid = start + ((end - start) >> 1);
        mSort(arr, start, mid);
        mSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

private static void merge(int[] arr, int start, int mid, int end) {
    int left1 = start, left2 = mid + 1, p = start;
    int[] tmp = new int[arr.length];
    while(left1 <= mid && left2 <= end) {
        if(arr[left1] < arr[left2]) {
            tmp[p++] = arr[left1++];
        }else {
            tmp[p++] = arr[left2++];
        }
    }
    while(left1 <= mid)
        tmp[p++] = arr[left1++];
    while(left2 <= end)
        tmp[p++] = arr[left2++];
    //copy
    while(start <= end) {
        arr[start] = tmp[start++];
    }
}

public static int[] heapSort(int[] arr) {
    for(int i = arr.length / 2; i >=0; i--) {
        buildMaxHeap(arr, arr.length, i);
    }
    for(int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        buildMaxHeap(arr, i, 0);
    }
    return arr;
}

private static void buildMaxHeap(int[] arr, int heapSize, int index) {
    int left  = index << 1;
    int right = (index <<1) + 1;
    int largestIndex = index;
    if(left < heapSize && arr[left] > arr[largestIndex]) largestIndex = left;
    if(right < heapSize && arr[right] > arr[largestIndex]) largestIndex = right;
    if(index != largestIndex) {
        swap(arr, index, largestIndex);
        buildMaxHeap(arr, heapSize, largestIndex);
    }
}

}
